package com.example.demo.lintcode;

import org.junit.Test;
import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.platform.commons.util.StringUtils;
import org.springframework.data.mongodb.core.aggregation.ArrayOperators;

import java.util.*;

/**
 * *  Author:zlf
 * *  2020/10/21 16:15
 **/
public class MainClass {

    @Test
    public void mainMethod() {
        try {
            int[] nums = new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3};
            removeDuplicates(nums);
            int a = 0;
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            while (i >= 2 && nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2] && nums[i] != Integer.MAX_VALUE) {
                for (int j = i; j < nums.length; j++) {
                    if ((j + 1) < nums.length) {
                        nums[j] = nums[j + 1];
                    }
                }
                nums[nums.length - 1] = Integer.MAX_VALUE;
                len--;
            }
        }
        return len;
    }

    public int myAtoi(String s) {
        s = s.replace(" ", "");
        if ("".equals(s)) {
            return 0;
        }
        String result = "";
        String nums = "1234567890";
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '-') {
                result += "-";
            } else if (nums.contains(String.valueOf(s.charAt(i)))) {
                result += s.charAt(i);
            } else if (s.charAt(i) == ' ' || s.charAt(i) == '+') {

            } else {
                if ("".equals(result)) {
                    result = "0";
                }
                break;
            }
        }
        boolean pre = result.startsWith("-");
        try {
            if (pre && result.length() == 1) {
                return 0;
            }
            int aa = Integer.parseInt(result);
            return aa;
        } catch (Exception e) {
            if (pre) {
                return -2147483648;
            } else {
                return 2147483647;
            }
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /*
            //case 1
            ListNode l1 = new ListNode(1);
            ListNode l2 = new ListNode(2);
            ListNode l3 = new ListNode(3);
            ListNode l4 = new ListNode(4);
            ListNode l5 = new ListNode(5);
            l1.next = l2;
            l2.next = l3;
            l3.next = l4;
            l4.next = l5;
            reverseBetween(l1, 2, 4);

            //case 2
            ListNode l1 = new ListNode(3);
            ListNode l2 = new ListNode(5);
            l1.next = l2;
            reverseBetween(l1, 1, 2);
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }
        List<ListNode> listNodes = new ArrayList<>();

        ListNode first = head;
        ListNode last = head;
        ListNode pre = null;
        if (left > 1) {
            pre = head;
        }
        ListNode next = null;
        int index = 1;
        while (true) {
            if (index < left) {
                pre = first;
                first = first.next;
            } else if (index == left) {
                listNodes.add(new ListNode(first.val));
                last = first;
            } else if (index < right) {
                last = last.next;
                listNodes.add(new ListNode(last.val));
            } else if (index == right) {
                last = last.next;
                listNodes.add(new ListNode(last.val));
                next = last.next;
                break;
            } else {
                break;
            }
            index++;
        }

        for (int i = 1; i < listNodes.size(); i++) {
            listNodes.get(i).next = listNodes.get(i - 1);
        }

        listNodes.get(0).next = next;
        if (pre != null) {
            pre.next = listNodes.get(listNodes.size() - 1);
            return head;
        } else {
            return listNodes.get(listNodes.size() - 1);
        }
    }

    /*
    int num = numDistinct("rabbbit", "rabbit");
    int num = numDistinct("babgbag", "bag");
     */
    public int numDistinct(String s, String t) {
        int count = 0;
        while (true) {
            if (count == s.length()) {
                break;
            }
            count++;
        }
        return 0;
    }


    //  String ss = convert("ABC", 1);
    public String convert(String s, int numRows) {
        int width = s.length() / 2 + 1;
        if (numRows == 1) {
            width = s.length();
        }
        char[][] a = new char[numRows][width];
        int x = 0;
        int y = 0;
        int type = 1;
        for (int i = 0; i < s.length(); i++) {
            if (type == 1) {
                a[x][y] = s.charAt(i);
                if (x >= (numRows - 1)) {
                    type = 2;
                } else {
                    x++;
                }
            } else {
                if (numRows != 1) {
                    x--;
                }
                y++;
                a[x][y] = s.charAt(i);
                if (x == 0) {
                    if (numRows != 1) {
                        x++;
                    } else {
                        y++;
                    }
                    type = 1;
                }
            }
        }
        String re = "";
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                if (a[i][j] != '\0') {
                    re += a[i][j];
                }
            }
        }
        return re;
    }

    public int reverse(int x) {
        String re = "";
        String data = String.valueOf(x);
        boolean isNagative = false;
        if (data.startsWith("-")) {
            data = data.substring(1);
            isNagative = true;
        }
        for (int i = data.length() - 1; i >= 0; i--) {
            re += data.charAt(i);
        }
        if (isNagative) {
            re = "-" + re;
        }
        try {
            return Integer.parseInt(re);
        } catch (Exception e) {
            return 0;
        }
    }

    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) {
                return s;
            } else {
                return String.valueOf(s.charAt(0));
            }
        }
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            int pre = i - 1;
            int next = i + 1;
            //奇数回文，以i为中心
            String temp = String.valueOf(s.charAt(i));
            while (true) {
                if (pre >= 0 && next < s.length()) {
                    if (s.charAt(pre) == s.charAt(next)) {
                        temp = s.substring(pre, next + 1);
                        pre--;
                        next++;
                    } else {
                        if (temp.length() > result.length()) {
                            result = temp;
                        }
                        break;
                    }
                } else {
                    if (temp.length() > result.length()) {
                        result = temp;
                    }
                    break;
                }
            }
            //偶数回文，i往后
            pre = i;
            next = i + 1;
            temp = "";
            while (true) {
                if (pre >= 0 && next < s.length()) {
                    if (s.charAt(pre) == s.charAt(next)) {
                        temp = s.substring(pre, next + 1);
                        pre--;
                        next++;
                    } else {
                        if (temp.length() > result.length()) {
                            result = temp;
                        }
                        break;
                    }
                } else {
                    if (temp.length() > result.length()) {
                        result = temp;
                    }
                    break;
                }
            }
        }
        return result;
    }

    public int lengthOfLongestSubstring(String s) {
        char[] temp = s.toCharArray();
        String a = "";
        int maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (a.contains(String.valueOf(temp[i]))) {
                if (a.length() > maxlength) {
                    maxlength = a.length();
                }
                a = a.substring(a.indexOf(temp[i]) + 1);
            }
            a += temp[i];
        }
        if (a.length() > maxlength) {
            maxlength = a.length();
        }
        return maxlength;
    }

    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int[] width = new int[2];
        int[] height = new int[2];
        width[0] = 0;
        width[1] = n;
        height[0] = 0;
        height[1] = n;
        int type = 1;
        int num = 1;
        while (true) {
            if (height[0] == height[1] || width[0] == width[1]) {
                break;
            }
            switch (type) {
                case 1:
                    for (int i = width[0]; i < width[1]; i++) {
                        result[height[0]][i] = num++;
                    }
                    type = 2;
                    height[0]++;
                    break;
                case 2:
                    for (int j = height[0]; j < height[1]; j++) {
                        result[j][width[1] - 1] = num++;
                    }
                    type = 3;
                    width[1]--;
                    break;
                case 3:
                    for (int i = width[1] - 1; i >= width[0]; i--) {
                        result[height[1] - 1][i] = num++;
                    }
                    type = 4;
                    height[1]--;
                    break;
                case 4:
                    for (int j = height[1] - 1; j >= height[0]; j--) {
                        result[j][width[0]] = num++;
                    }
                    type = 1;
                    width[0]++;
                    break;
            }
        }
        return result;
    }

    private List<Integer> spiralOrder(int[][] matrix) {
        int[] width = new int[2];
        int[] height = new int[2];
        width[0] = 0;
        width[1] = matrix[0].length;
        height[0] = 0;
        height[1] = matrix.length;
        List<Integer> result = new ArrayList<>();
        int type = 1;
        while (true) {
            if (height[0] == height[1] || width[0] == width[1]) {
                break;
            }
            switch (type) {
                case 1:
                    for (int i = width[0]; i < width[1]; i++) {
                        result.add(matrix[height[0]][i]);
                    }
                    type = 2;
                    height[0]++;
                    break;
                case 2:
                    for (int j = height[0]; j < height[1]; j++) {
                        result.add(matrix[j][width[1] - 1]);
                    }
                    type = 3;
                    width[1]--;
                    break;
                case 3:
                    for (int i = width[1] - 1; i >= width[0]; i--) {
                        result.add(matrix[height[1] - 1][i]);
                    }
                    type = 4;
                    height[1]--;
                    break;
                case 4:
                    for (int j = height[1] - 1; j >= height[0]; j--) {
                        result.add(matrix[j][width[0]]);
                    }
                    type = 1;
                    width[0]++;
                    break;
            }
        }
        return result;
    }


    // (1+(4+5+2)-3)+(6+8)
    //基本计算器
    private int calculate(String s) {
        String temp = s.replace(" ", "");
        while (temp.contains("(")) {
            int rindex = temp.lastIndexOf("(");
            char[] aaa = temp.toCharArray();
            for (int i = 0; i < aaa.length; i++) {
                if (aaa[i] == ')' && i > rindex) {
                    String tempStr = temp.substring(rindex, i + 1);
                    int result = dealbaseStr(aaa, rindex, i);
                    temp = temp.replace(tempStr, String.valueOf(result));
                    break;
                }
            }
        }
        return dealbaseStr(temp.toCharArray(), -1, temp.length());
    }

    //1+3-2
    private int dealbaseStr(char[] aaa, int rIndex, int lIndex) {
        String tempOp = "";
        String tempNum = "0";
        int lastNum = 0;
        String lastStr = "";
        for (int i = rIndex + 1; i < lIndex; i++) {
            if (tempNum.length() > 1 && tempNum.startsWith("0")) {
                tempNum = tempNum.substring(1);
            }

            if (!lastStr.equals("-") && (aaa[i] == '+' || aaa[i] == '-')) {
                if (!"".equals(tempOp)) {
                    lastNum = basecalc(tempOp, lastNum, Integer.parseInt(tempNum));
                } else {
                    lastNum = Integer.parseInt(tempNum);
                }
                tempOp = String.valueOf(aaa[i]);
                tempNum = "0";
            } else {
                tempNum = tempNum + aaa[i];
            }
            lastStr = String.valueOf(aaa[i]);
        }
        if (!"".equals(tempOp)) {
            lastNum = basecalc(tempOp, lastNum, Integer.parseInt(tempNum));
        } else {
            lastNum = Integer.parseInt(tempNum);
        }
        return lastNum;
    }

    private int basecalc(String op, int num1, int num2) {
        if ("+".equals(op)) {
            return num1 + num2;
        } else if ("-".equals(op)) {
            return num1 - num2;
        }
        return 0;
    }


    // int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
    //   int[][] envelopes = {{30, 50}, {12, 2}, {3, 4}, {12, 15}};

    public int maxEnvelopes(int[][] envelopes) {

        for (int i = 0; i < envelopes.length; i++) {
            for (int j = i + 1; j < envelopes.length; j++) {
                if (envelopes[i][0] > envelopes[j][0]) {
                    int[] temp = envelopes[j];
                    envelopes[j] = envelopes[i];
                    envelopes[i] = temp;
                } else if (envelopes[i][0] == envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    int[] temp = envelopes[j];
                    envelopes[j] = envelopes[i];
                    envelopes[i] = temp;
                }
            }
        }
        int maxwidth = 0;
        int maxheight = 0;
        int count = 1;
        for (int i = 0; i < envelopes.length; i++) {
            for (int j = i + 1; j < envelopes.length; j++) {
                if ((envelopes[i][0] < envelopes[j][0]) && (envelopes[i][1] < envelopes[j][1])) {
                    if ((maxwidth == 0 && maxheight == 0) ||
                            (maxwidth != 0 && maxheight != 0 && maxwidth < envelopes[j][0] && maxheight < envelopes[j][1])) {
                        count++;
                        i = j - 1;
                        maxwidth = envelopes[j][0];
                        maxheight = envelopes[j][1];
                        break;
                    }
                }
            }
        }
        return count;
    }

    //    jump(new int[]{1, 2});
//    jump(new int[]{1, 3, 2});
//    jump(new int[]{3, 2, 1});
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int temp = 0;
            int maxindex = 0;
            for (int j = i + 1; j <= (i + nums[i]); j++) {
                if (j == nums.length) {
                    break;
                }
                if ((nums[j] - (j - i - 1)) > temp) {
                    temp = nums[j];
                    maxindex = j;
                }
            }
            if (maxindex != 0) {
                i = maxindex - 1;
                count++;
            }
            if (nums[i] >= nums.length) {
                if (i == 0) {
                    count++;
                }
                break;
            }
        }
        System.out.println(count);
        return count;
    }

    private String toBinaryString(int num) {
        String str = "";
        while (num != 0) {
            str = num % 2 + str;
            num = num / 2;
        }
        return str;
    }

    private int[] countBits(int num) {
        int[] Bits = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            Bits[i] = Integer.toBinaryString(i).replace("0", "").length();
        }
        return Bits;
    }


    /**
     * @param a:
     * @param b:
     * @param h:
     * @return: Return the area of trapezoid
     */
    public double AreaOfTrapezoid(int a, int b, int h) {
        // Write your code here
        return (a + b) * h / 2.0;
    }

    public int getSum(int A, int B) {
        // Write your code here
        int total = 0;
        for (int i = A; i <= B; i++) {
            if (i % 3 == 0) {
                total += i;
            }
        }
        return total;
    }

    /**
     * 设计一种方法，通过给重复字符计数来进行基本的字符串压缩。
     * <p>
     * 例如，字符串 aabcccccaaa 可压缩为 a2b1c5a3 。而如果压缩后的字符数不小于原始的字符数，则返回原始的字符串。
     * <p>
     * 可以假设字符串仅包括 a-z 的字母。
     */
    public String compress(String originalString) {
        // write your code here
        StringBuilder result = new StringBuilder();
        char last = '!';
        int count = 0;
        for (int i = 0; i < originalString.length(); i++) {
            if (last == '!') {
                result.append(originalString.charAt(i));
                count++;
                last = originalString.charAt(i);
                continue;
            }
            if (originalString.charAt(i) == last) {
                count++;
            } else {
                result.append(count);
                count = 1;
                result.append(originalString.charAt(i));
                last = originalString.charAt(i);
            }
            if (i == originalString.length() - 1) {
                result.append(count);
            }
        }
        if (result.length() < originalString.length()) {
            return result.toString();
        } else {
            return originalString;
        }
    }

    public int numberofDistinctIslands(int[][] grid) {
        // write your code here
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {


            }
        }
        return 0;
    }

    public String reverseWords(String s) {
        // write your code here
        String[] temp = s.split(" +");
        StringBuilder sb = new StringBuilder();
        for (int i = temp.length - 1; i >= 0; i--) {
            sb.append(" ");
            sb.append(temp[i]);
        }
        if (sb.toString().length() > 1) {
            return sb.toString().substring(1);
        } else
            return sb.toString();
    }


    public static long concurrentTime1, concurrentTime2, concurrentMemory1, concurrentMemory2;

    @BeforeEach
    public void before() {
        //得到程序开始时的系统时间（纳秒级，最终转化毫秒，保留小数点后两位）
        concurrentTime1 = System.nanoTime();
        //得到虚拟机运行、程序开始执行时jvm所占用的内存。
        Runtime runtime = Runtime.getRuntime();
        concurrentMemory1 = runtime.totalMemory() - runtime.freeMemory();
    }

    @AfterEach
    public void after() {
        //得到程序执行完毕时的系统时间（毫秒级）
        concurrentTime2 = System.nanoTime();
        //得到虚拟机运行、所要测试的执行代码执行完毕时jvm所占用的内存（byte）。
        Runtime runtime = Runtime.getRuntime();
        concurrentMemory2 = runtime.totalMemory() - runtime.freeMemory();

        //计算start和end之间的代码执行期间所耗时间(ms)与内存(M)。
        // 1毫秒(ms) = 1000微秒(us) = 1000 000纳秒(ns)
        // 1M = 1*2^20 byte = 1024 * 1024 byte;
        String time = String.valueOf((double) (concurrentTime2 - concurrentTime1) / 1000000);
        String memory = String.valueOf((double) (concurrentMemory2 - concurrentMemory1) / 1024 / 1024);
        System.out.println("---------------您的代码执行时间为：" + time.substring(0, time.equals("0.0") ? 1 : (time.indexOf(".") + 3)) + " ms, 消耗内存：" + memory.substring(0, memory.equals("0.0") ? 1 : (memory.indexOf(".") + 3)) + " M + !---------------");
    }


}
